package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/5/29 19:24
 * @description:
 */
public class HasPath12 {

    public static void main(String[] args) {
        char [] [] arr = {{'a','b','c','e'},{'s','f','c','s'}, {'a','d','e','e'}}; //[[a,b,c,e],[s,f,c,s],[a,d,e,e]]
        String word = "see";
        boolean flag = new HasPath12().hasPath(arr, word);
        System.out.println(flag);
    }

    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        //判断特殊条件
        if(matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0){
            return false;
        }
        //双层循环
        int n = matrix.length;
        int m = matrix[0].length;
        //创建标记的矩阵
        boolean[][] isVisited = new boolean[n][m];
        //任意的起始点 i j
        for(int i=0; i< n; i++){
            for(int j=0; j<m; j++){
                //起始点相同，开始dfs搜索
                 if(dfs(matrix, word, i, j, isVisited, 0)){
                     return true;
                 }
            }
        }
        return false;
    }
    //参数说明，n表示当前访问到第几个字符了，（x,y）表示当前要访问的字符在board中的坐标
    public boolean dfs(char[][] arr, String word, int i, int j, boolean[][] isVisited, int n){
        //停止条件 isVisited[i][j] 是否遍历过
        if(i>=arr.length||i<0||j>=arr[0].length||j<0|| isVisited[i][j]){
            return false;
        }

        //当前位置和我们需要的字符word.charAt(n)不同，该路径行不通
        if(arr[i][j] != word.charAt(n)){
            return false;
        }
        //我们要查找的最后一个字符都通过了上面那条if语句，该单词路径存在
        if(n == word.length()-1){
            return true;
        }

        //标记board[x][y]已经被访问过了
        isVisited[i][j] = true;
        //上面条件不满住， 四个方向上下左右
        boolean flag = dfs(arr, word, i+1, j, isVisited, n+1) ||
                dfs(arr, word, i, j+1, isVisited, n+1) ||
                dfs(arr, word, i-1, j, isVisited, n+1) ||
                dfs(arr, word, i, j-1, isVisited, n+1);

        isVisited[i][j] = false;//状态回退
        return flag;
    }
}
